package ex.algorithms.sorting;

public class MergeSort {
	public static void sortIncreasing(int[] input) {
		if(input == null || input.length < 2)
			return;
		
		sortIncreasing(input, 0, input.length-1);
		
	}
	
	public static void sortIncreasing(int[] input, int start, int end) {
		if(end == start)
			return;
		
		int midPoint = (end + start) / 2;
		
		sortIncreasing(input, start, midPoint);
		sortIncreasing(input, midPoint+1, end);
		
		merge(input, start, midPoint, end);
	}
	
	public static void merge(int[] input, int start, int middle, int end) {
		int leftLength = middle - start + 1;
		int rightLength = end - middle;
		
		int[] left = new int[leftLength];
		int[] right = new int[rightLength];
		
		for(int i=0; i<leftLength; i++)
			left[i] = input[i+start];
		
		for(int i=0; i<rightLength; i++)
			right[i] = input[i+middle+1];
		
		
		int i=0;
		int j=0;
		for(int k=start; k<=end; k++) {
			if(i == left.length) {
				input[k] = right[j];
				j++;
				continue;
			}
			if(j == right.length) {
				input[k] = left[i];
				i++;
				continue;
			}
			
			if(left[i] <= right[j]) {
				input[k] = left[i];
				i++;
			}
			else {
				input[k] = right[j];
				j++;
			}
		}
	}
}
